/**
 * 求字符串[s1, s2]之间不以evil做子串的串的数量
 * s1与s2长度均为n。
 * 
 * 用数位DP即可。
 * 设D[510][55]，Dij，i表示搜索到i位、j表示已经匹配了j个
 * 当前数位如果与evil[j]相等，就可以加一
 * 否则要利用特征数组查看匹配长度，据说直接暴力枚举也可以
 * 注意不匹配时特征数组的用法
 * 
 * 可能用上下界数位DP更好
 * 这里无需用s1减减，因为如果是全a串不太方便。
 * 只需要特判s1是否包含evil即可
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

template<typename T>
ostream & operator << (ostream & os, const vector<T> & v){
    for(auto i : v) os << i << " ";
    return os;
}

using llt = long long;
const llt MOD = 1E9 + 7;

vector<int> Next;
vector<int> Pattern;

template<typename IT = const char *>
void calcNext(IT begin, int n, vector<int> & next) {
    next.assign(n, 0);
    for(int i=1;i<n;++i){
        int k = next[i - 1];
        while(k > 0 and *(begin + i) != *(begin + k)){
            k = next[k - 1];
        }
        next[i] = (*(begin + i) == *(begin + k)) ? k + 1 : 0;
    }
    return;
}

vector<int> G;
llt D[510][55];

llt dfs(int pos, int match, bool lead, bool limit){
    if(-1 == pos) {
        return 1; //
    }
    if(not lead and not limit and -1 != D[pos][match]) {
        return D[pos][match];
    }
    int last = limit ? G[pos] : 26; // 'z'变为26
    
    llt ans = 0;
    for(int i=1;i<=last;++i){
        // 利用next数组
        auto st = match;
        while(st and Pattern[st] != i) st = Next[st - 1];
        // 出循环后存在两种可能
        if(Pattern[st] == i){
            if(st + 1 < Pattern.size()){
                ans += dfs(pos - 1, st + 1, lead&&0==i, limit&&last==i);
            }
        }else{
            ans += dfs(pos - 1, 0, lead&&0==i, limit&&last==i);  
        }
        ans %= MOD;
    }

    if(not lead and not limit){
        D[pos][match] = ans;
    }    
    return ans;
}

llt digitDP(const string & s){
    G.clear();
    for(auto it=s.rbegin();it!=s.rend();++it){
        G.emplace_back(*it - 'a' + 1);
    }
    return dfs(G.size()-1, 0, true, true);
}

class Solution {
public:
    int findGoodStrings(int n, string s1, string s2, string evil) {
        memset(D, -1, sizeof(D));
        calcNext(evil.begin(), evil.length(), Next);

        Pattern.clear();
        for(auto it=evil.begin();it!=evil.end();++it){
            Pattern.push_back(*it - 'a' + 1);
        }

        auto t2 = digitDP(s2);
        auto t1 = digitDP(s1);    
        if(search(s1.begin(), s1.end(), evil.begin(), evil.end()) == s1.end()) t2 += 1;
        return ((t2 - t1) % MOD + MOD) % MOD; 
    }
};

